/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 晓星航
 * Date: 2023-11-14
 * Time: 10:25
 */
public class MaxMinPairFinder {
    public static void main(String[] args) {
        int[] arr = {3, 8, 1, 4, 9, 2, 6, 5, 7};
        Pair result = findMaxMinPair(arr, 0, arr.length - 1);
        System.out.println("Max numbers: " + result.max1 + ", " + result.max2);
        System.out.println("Min numbers: " + result.min1 + ", " + result.min2);
    }

    static class Pair {
        int max1, max2, min1, min2;
    }

    static Pair findMaxMinPair(int[] arr, int low, int high) {
        Pair result = new Pair();
        if (high - low == 1) {
            if (arr[low] < arr[high]) {
                result.min1 = arr[low];
                result.max1 = arr[high];
            } else {
                result.min1 = arr[high];
                result.max1 = arr[low];
            }
            result.min2 = result.min1;
            result.max2 = result.max1;
        } else if (high - low == 0) {
            result.min1 = arr[low];
            result.max1 = arr[low];
            result.min2 = arr[low];
            result.max2 = arr[low];
        } else {
            int mid = (low + high) / 2;
            Pair leftResult = findMaxMinPair(arr, low, mid);
            Pair rightResult = findMaxMinPair(arr, mid + 1, high);

            result.min1 = Math.min(leftResult.min1, rightResult.min1);
            result.min2 = Math.min(Math.max(leftResult.min1, rightResult.min1), Math.min(leftResult.min2, rightResult.min2));

            result.max1 = Math.max(leftResult.max1, rightResult.max1);
            result.max2 = Math.max(Math.min(leftResult.max1, rightResult.max1), Math.max(leftResult.max2, rightResult.max2));
        }
        return result;
    }
}
